package leetcode

import "container/heap"

type ListNode struct {
	Val  int
	Next *ListNode
}

type MyList []*ListNode

func (list MyList) Len() int {
	return len(list)
}

func (list MyList) Less(a, b int) bool {
	return list[a].Val < list[b].Val
}

func (list MyList) Swap(a, b int) {
	list[a], list[b] = list[b], list[a]
}

func (list *MyList) Push(x any) {
	*list = append(*list, x.(*ListNode))
}
func (list *MyList) Pop() any {
	length := len(*list) - 1
	res := (*list)[length]
	*list = (*list)[0:length]
	return res
}

func mergeKLists(lists []*ListNode) *ListNode {

	var pq MyList
	for _, ptr := range lists {
		if ptr != nil {
			pq = append(pq, ptr)
		}
	}

	heap.Init(&pq)
	resHead := ListNode{Val: 0, Next: nil}
	resTail := &resHead

	for (&pq).Len() != 0 {
		resTail.Next = heap.Pop(&pq).(*ListNode)
		resTail = resTail.Next
		if resTail.Next != nil {
			heap.Push(&pq, resTail.Next)
		}
	}
	return resHead.Next
}
